/*
 * Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. 
The new list should be made by splicing together the nodes of the first two lists.
 */
package com.xinpan.exercise;

public class MergeTwoSortedList {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(l1 == null)
            return l2;
        else if(l2 == null)
            return l1;
            
        ListNode head = null;
        ListNode cur = null;
        while(l1 != null && l2 != null)
        {
            ListNode aNode = null;
            
            if(l1.val < l2.val)
            {
                aNode = l1;
                l1 = l1.next;
            }
            else
            {
                aNode = l2;
                l2 = l2.next;
            }
            if(head == null)
            {
                head = aNode;
                cur = head;
            }
            else
            {
                cur.next = aNode;
                cur = cur.next;
            }
        }
        while(l1 != null)
        {
            cur.next = l1;
            cur = cur.next;
            l1 = l1.next;
        }
        while(l2 != null)
        {
            cur.next = l2;
            cur = cur.next;
            l2 = l2.next;
        }
        return head;
    }
    
     public class ListNode {
    	      int val;
    	      ListNode next;
    	      ListNode(int x) {
    	          val = x;
    	          next = null;
    	      }
     }
}
